package com.leetcode.algorithm.topic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 二叉树相关算法题解
 * 
 * (done)144. 二叉树的前序遍历
 * (done)94. 二叉树的中序遍历
 * (done)145. 二叉树的后序遍历
 * (done)102. 二叉树的层次遍历
 * (done)104. 二叉树的最大深度
 * (done)111. 二叉树的最小深度
 * @author: jie.deng
 * @time: 2019年3月13日 下午11:49:31
 */
public class BinaryTreeSolution {
	/**
     * 144. 二叉树的前序遍历
     * 
     * 给定一个二叉树，返回它的 前序 遍历。
     * 
     *  示例:
     * 
     * 输入: [1,null,2,3]  
     *    1
     *     \
     *      2
     *     /
     *    3 
     * 
     * 输出: [1,2,3]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			list.add(node.val); // 遍历当前结点
			if (node.right != null) { // 入栈顺序为先右孩子后左孩子，以确保出栈时的顺序是先左后右
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}
		return list;
	}
	
    /**
     * 94. 二叉树的中序遍历
     * 
     * 给定一个二叉树，返回它的中序 遍历。
     * 
     * 示例:
     * 
     * 输入: [1,null,2,3]
     *    1
     *     \
     *      2
     *     /
     *    3
     * 
     * 输出: [1,3,2]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		TreeNode cur = root;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		while (cur != null || !stack.isEmpty()) { // 划重点
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				list.add(cur.val); // 遍历当前结点
				cur = cur.right;
			}
		}
		return list;
	}
	
	/**
     * 145. 二叉树的后序遍历
     * 
     * 给定一个二叉树，返回它的 后序 遍历。
     * 
     * 示例:
     * 
     * 输入: [1,null,2,3]  
     *    1
     *     \
     *      2
     *     /
     *    3 
     * 
     * 输出: [3,2,1]
     * 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
     * @param root
     * @return
     */
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		TreeNode pre = null; // 划重点:记录上次遍历的结点
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode cur = stack.peek(); // 先判断下孩子结点是否遍历完成
			if ((cur.left == null && cur.right == null) || ((cur.right == null ? cur.left : cur.right) == pre)) {
				// 划重点:如果当前结点没有孩子或者上次遍历的结点为左孩子(没有右孩子的情况)或者右孩子，则遍历当前结点
				stack.pop();
				list.add(cur.val);// 遍历当前结点
				pre = cur;
			} else {
				// 需要先遍历孩子结点，孩子入栈
				// 入栈顺序为先右孩子后左孩子，以确保出栈时的顺序是先左后右
				if (cur.right != null) {
					stack.push(cur.right);
				}
				if (cur.left != null) {
					stack.push(cur.left);
				}
			}
		}
		return list;
	}
	
	/**
     * 102. 二叉树的层次遍历
     * 
     * 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
     * 
     * 例如:
     * 给定二叉树: [3,9,20,null,null,15,7],
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其层次遍历结果：
     * 
     * [
     *   [3],
     *   [9,20],
     *   [15,7]
     * ]
     * @param root
     * @return
     */
	public List<List<Integer>> levelOrder(TreeNode root) {
		// 广度优先搜索，使用队列实现，先进先出
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			List<Integer> levelList = new ArrayList<Integer>();
			int size = queue.size(); // 当前层次结点个数
			for (int i = 0; i < size; i++) {// 遍历当前层
				TreeNode node = queue.poll();
				levelList.add(node.val); // 遍历当前结点
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			list.add(levelList);
		}
		return list;
	}
    
	/**
     * 104. 二叉树的最大深度
     * 给定一个二叉树，找出其最大深度。
     * 
     * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例：
     * 给定二叉树 [3,9,20,null,null,15,7]，
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最大深度 3 。
     * @param root
     * @return
     */
	public int maxDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	
	/**
	 * 111. 二叉树的最小深度
	 * 
     * 给定一个二叉树，找出其最小深度。
     * 
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例:
     * 
     * 给定二叉树 [3,9,20,null,null,15,7],
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回它的最小深度  2.
	 * @param root
	 * @return
	 */
	public int minDepth(TreeNode root) {
		int depth = 0;
		if (null == root) {
			return depth;
		}
		depth += 1; // 加上当前节点深度1
		if (root.left != null && root.right != null) {
			depth += Math.min(minDepth(root.left), minDepth(root.right));
		} else {
			if (root.left != null) {
				depth += minDepth(root.left);
			} else if (root.right != null) {
				depth += minDepth(root.right);
			}
		}
		return depth;
	}
	
}